/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
bool isPail(struct ListNode* head ) {
    // write code here
    //1、反转链表的后半部分
    //快慢指针查找链表中点
    struct ListNode *fast = head, *slow = head;
    while(fast->next != NULL && fast->next->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    slow = slow->next;
     
    //反转链表的后半部分
    struct ListNode *headtail = slow, *newHead = NULL;
    struct ListNode *tmp;
    while(headtail != NULL){
        tmp = headtail->next;
        headtail->next = newHead;
        newHead = headtail;
        headtail = tmp;
    }
     
    //比较前后两部分是否完全相同
    struct ListNode *headfore = head;
    while(newHead != NULL){//后半段的长度小于等于前半段，所以以后半段是否结束作为循环结束判断
        if(headfore->val != newHead->val)
            return false;
        headfore = headfore->next;
        newHead = newHead->next;
    }
     
    return true;
}